package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class LC14 {
    public static void main(String[] args) {
        LC14 lc14 = new LC14();
        System.out.println(Arrays.deepToString(lc14.merge(new int[][]{{1, 4}, {2, 3}})));
        System.out.println(Arrays.deepToString(lc14.merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}})));
    }
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparing(ints -> ints[0]));
        int[][] ans = new int[intervals.length][2];
        int x = 0;
        ans[x] = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if(ans[x][1] >= intervals[i][0]){
                if(ans[x][1] < intervals[i][1])
                    ans[x][1] = intervals[i][1];
            }else {
                x++;
                ans[x] = intervals[i];
            }
        }
        return Arrays.copyOf(ans,++x);
    }

    // [1,4],[5,6]
    public int[][] merge1(int[][] intervals) {
        int[] ansint = new int[10001];
        int max = 0;
        for(int i = 0; i < intervals.length; i++){
            int left;
            int right = intervals[i][1];
            max = Math.max(max,right);
            for(left = intervals[i][0];left<=right;left++){
                ++ansint[left];
            }
        }
        List<Integer[]> ans1 = new ArrayList<>();
        int[][] ans = new int[intervals.length][2];
        int left = 0;
        int x = 0;
        for(int i = 1; i <= max; i++){
            if(ansint[i-1] == 0){
                left = i;
                continue;
            }
            if(ansint[i-1] != 0 && ansint[i+1] == 0 && ansint[i] != 0){
                ans1.add(new Integer[]{left,i});
                ans[x][0] = left;
                ans[x][1] = i;
                x++;
            }
        }
//        System.out.println(ans1);
//        System.out.println(Arrays.deepToString());
        return Arrays.copyOf(ans, x);
    }
}
